package 数组和链表;


import 抽象数据类型.ListNode;

/**
 * @Description:
 * @Author: Administrator
 * @Date: 2020-04-27
 */

public class SymbolList {

    public static  void printNode(ListNode root) {
        while (root != null) {
            System.out.println(root.val);
            root = root.next;
        }
    }
    public static ListNode buildList(int[] arr) {
        ListNode root = new ListNode(arr[0]);
        ListNode current = root;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current= current.next;
        }
        return root;
    }
    //
    public ListNode Symbol(ListNode root) {

        ListNode oneStep = root;
        ListNode twoStep = root;
        while (twoStep.next != null&&twoStep.next.next!=null) {
            oneStep = oneStep.next;
            twoStep = twoStep.next.next;
        }
        ListNode midNode = oneStep;
        if (twoStep.next != null) {
            midNode = oneStep.next;
        }
        ListNode reverseNode = reverseNode(midNode);
        ListNode head = root;

        while (reverseNode.next != null) {
            ListNode tempNode = head.next;
            head.next = reverseNode;
            ListNode currNode = reverseNode.next;
            reverseNode.next = tempNode;
            head = tempNode;
            reverseNode = currNode;
        }

        return root;
    }
    public ListNode SymbolTwo(ListNode root) {

        ListNode oneStep = root;
        ListNode twoStep = root;
        while (twoStep.next != null&&twoStep.next.next!=null) {
            oneStep = oneStep.next;
            twoStep = twoStep.next.next;
        }
        ListNode midNode = oneStep;
        if (twoStep.next != null) {
            midNode = oneStep.next;
        }
       

        return root;
    }
    public static ListNode reverseNode(ListNode head) {
        ListNode preNode = null, nextNode = null;
        while (head != null) {
            nextNode = head.next;
            //倒置指针
            head.next=preNode;
            preNode = head;
            head = nextNode;

        }
        return preNode;
    }
    public static  int InversePairs(int [] arr) {
        int count=0;
        for(int i=0;i<arr.length;i++) {
            for(int j=i+1;j<arr.length;j++) {
                if(arr[i]>arr[j]) {
                    count++;
                }
            }
        }
        return count%1000000007;

    }
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8,0};
        SymbolList sysmbolList = new SymbolList();
        ListNode root = sysmbolList.buildList(arr);
        sysmbolList.printNode(reverseNode(root));
        sysmbolList.printNode(new SymbolList().Symbol(root));

        System.out.println(InversePairs(arr));
    }
}
